import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Author: 笨蛋超人不会飞
 * Date:  12:32
 */
public class question_47 {
}
class Solution_47 {
    HashMap<String,List<Integer>> map;
    public List<List<Integer>> permuteUnique(int[] nums) {
        map=new HashMap<>();
//        特殊判断
        if(nums==null||nums.length==0){
            return null;
        }
//        设置结果集
        List<List<Integer>> result=new ArrayList<>();
        if(nums.length==1){
            List<Integer> list=new ArrayList<>();
            list.add(nums[0]);
            result.add(list);
            return result;
        }
        int len=nums.length;
        //默认值是0
        int[] tag_arr=new int[len];
        List<Integer> temp_list=new ArrayList<>();
        df(result,temp_list,tag_arr,nums);
        result= map.values()
                .stream()
                .collect(Collectors.toList());
        return result;
    }
    private void df(List<List<Integer>> result, List<Integer> temp_list, int[] tag_arr, int[] nums) {
        if (temp_list.size()==nums.length){
            StringBuilder sb = new StringBuilder();
            for (Integer number : temp_list) {
                sb.append(number.toString());
            }
            String key = sb.toString();
            map.put(key,new ArrayList<>(temp_list));
            return;
        }
        for (int i = 0; i < tag_arr.length; i++) {
            if(tag_arr[i]==0){
                tag_arr[i]=1;
                temp_list.add(nums[i]);
                df(result,temp_list,tag_arr,nums);
                //进行还原
                tag_arr[i]=0;
                temp_list.remove(temp_list.size()-1);
            }


        }
    }
    private void backtrack(List<List<Integer>> results, List<Integer> tempList, int[] nums, boolean[] used) {
        if (tempList.size() == nums.length) {
            results.add(new ArrayList<>(tempList)); // 找到一个解
        } else {
            for (int i = 0; i < nums.length; i++) {
                if (used[i] || (i > 0 && nums[i] == nums[i-1] && !used[i-1])) {
                    // 跳过已经使用的数字或者重复的数字（除非前一个重复数字已经被使用过）
                    continue;
                }
                used[i] = true;
                tempList.add(nums[i]);
                backtrack(results, tempList, nums, used);
                used[i] = false; // 回溯
                tempList.remove(tempList.size() - 1);
            }
        }
    }

}
